package demo;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-06-21
 * Time: 8:17
 */
public class TestDemo {

    public static void merge(int[] nums,int left,int mid,int right){
        int s1= left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int[] tmp = new int[nums.length];
        int k =0;
        while(s1<=e1&&s2<=e2){
            if(nums[s1]<nums[s2]){
                tmp[k++] = nums[s1++];
            }else {
                tmp[k++] = nums[s2++];
            }
        }
        while(s1<=e1){
            tmp[k++] = nums[s1++];
        }
        while(s2<=e2){
            tmp[k++] = nums[s2++];
        }
        //将其拷贝回原数组
        for(int i =0;i<k;++i){
            nums[i+left] = tmp[i];
        }

    }

    public static void mergeSort(int[] nums,int left,int right){
        if(left>=right){
            return;
        }
        int mid = (left+right)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        //都有序进行归并
        merge(nums,left,mid,right);
    }

    //归并排序非递归版本

    public static void mergeSortNor(int[] nums,int left,int right){
        int gap =1;
        int mid = (left+right)>>>1;
        while(gap<nums.length){
            for(int i =0;i<nums.length;i+=2*gap){
                left =i;
                mid = left+gap-1;
                if(mid>=nums.length){
                    mid = nums.length-1;
                }
                right = mid+gap;
                if(right>=nums.length){
                    right = nums.length-1;
                }
                merge(nums,left,mid,right);
            }
            gap*=2;
        }
    }

    public static void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    //快速排序hoare法
    public static int hoare(int[] nums,int left,int right){
        int pivot = left;

        while(left<right){
            //右边找比pivot位置元素小的
            while(left<right&&nums[right]>=nums[pivot]){
                right--;
            }
            //左边找比pivot位置大的元素
            while(left<right&&nums[left]<=nums[pivot]){
                left++;
            }
            swap(nums,left,right);
        }
        //两者相遇更新基准元素
        swap(nums,left,pivot);
        return left;
    }


    //快速排序非递归版本
    public static void QuickSortNor(int[] nums,int left,int right){
        Stack<Integer> stack = new Stack<>();
        int mid = hoare(nums,left,right);
        if(left<mid-1){
            stack.push(left);
            stack.push(mid-1);
        }
        if(right>mid+1){
            stack.push(mid+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            mid = hoare(nums,left,right);
            if(left<mid-1){
                stack.push(left);
                stack.push(mid-1);
            }
            if(right>mid+1){
                stack.push(mid+1);
                stack.push(right);
            }
        }
    }

    //计数排序

    public static int[] countSort(int[] nums,int left,int right){
        //寻找数组中的最大值和最小值
        int max = nums[0];
        int min = nums[0];
        for(int i =1;i<nums.length;++i){
            if(max<nums[i]){
                max = nums[i];
            }
            if(min>nums[i]){
                min = nums[i];
            }
        }
        int[] count = new int[max-min+1];
        //开始进行计数
        for(int i =0;i<nums.length;++i){
            count[nums[i]-min]++;
        }
        //输出到tmp这个数组中
        int[] tmp = new int[nums.length];
        int index =0;
        for(int i =0;i<count.length;++i){
            while(count[i]>0){
                tmp[index++] = i+min;
                count[i]--;
            }
        }
        return tmp;

    }


    public static void main(String[] args) {
        //归并排序递归版
        int[] nums = {10,6,7,1,3,9,4,2,5,6,9,7};

        int[] tmp = countSort(nums,0,nums.length-1);

        System.out.println(Arrays.toString(tmp));
    }

}
